package ClassLib;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;
import java.util.*;

public class libof202409_3 {
    //https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
       //中序能够从小到大
//        LinkedList<Integer> res1 = new LinkedList<>();
//        LinkedList<Integer> res2 = new LinkedList<>();
//        traverseTree(root1,res1);
//        traverseTree(root2,res2);
//        List<Integer> res = new ArrayList<>();
//        while (!res1.isEmpty() && !res2.isEmpty()) {
//            if(res1.peekFirst() <= res2.peekFirst()){
//                res.add(res1.pollFirst());
//            }
//            else res.add(res2.pollFirst());
//        }
//        if(!res1.isEmpty()) res.addAll(res1);
//        if(!res2.isEmpty()) res.addAll(res2);
//        return res;
        BSTIterator itr = new BSTIterator(root1);
        BSTIterator itr2 = new BSTIterator(root2);
        List<Integer> res = new ArrayList<>();
        while (itr.hasNext() && itr2.hasNext()) {
            if(itr.peek()<=itr2.peek()){
                res.add(itr.next());
            }
            else{res.add(itr2.next());}
        }
        while (itr.hasNext()){res.add(itr.next());}
        while (itr2.hasNext()){res.add(itr2.next());}
        return res;
    }

//    private void traverseTree(TreeNode root, LinkedList<Integer> res) {
//        if(root==null) return;
//        traverseTree(root.left,res);
//        res.addLast(root.val);
//        traverseTree(root.right,res);
//    }
    public class BSTIterator {
       Stack<TreeNode> stk;
        public BSTIterator(TreeNode root) {
            stk=new Stack<>();
            pushLeftBranch(root);
        }

        private void pushLeftBranch(TreeNode root) {
            if(root==null) return;
            while (root!=null) {
                stk.push(root);
                root = root.left;
            }
        }
       public int peek(){
            return stk.peek().val;
       }
        public int next() {
            TreeNode pop = stk.pop();
            pushLeftBranch(pop.right);
            return pop.val;
        }

        public boolean hasNext() {
         return !stk.isEmpty();
        }
    }
   //https://leetcode.cn/problems/interleaving-string/ 以下的变量 diff  pick 可以全部移除掉，原因是他分割必然diff 不会大于1 的，画图就知道了
//   public boolean isInterleave(String s1, String s2, String s3) {
//       if (s1.length() + s2.length() != s3.length()) return false;
//       int[][] memo=new int[s1.length()+1][s2.length()+1];
//       for (int[] arr : memo) {
//           Arrays.fill(arr, -1);
//       }
//       return isInterleave(s1, 0, s2, 0, s3, 0, -1, 0,memo);
//   }
//
//    private boolean isInterleave(String s1, int i, String s2, int j, String s3, int t, int pick, int diff,int[][] memo) {
//        if (i == s1.length() && j == s2.length() && t == s3.length()) return true;
//        if (Math.abs(diff) > 1) return false;
//        if(memo[i][j]!=-1) return memo[i][j] == 1;
//        boolean ans = false;
//        if (i < s1.length() && s1.charAt(i) == s3.charAt(t)) {
//            ans = isInterleave(s1, i + 1, s2, j, s3, t + 1, 0, pick == 0 ? diff : diff + 1,memo);
//        }
//        if (j < s2.length() && s2.charAt(j) == s3.charAt(t)) {
//            ans = ans || isInterleave(s1, i, s2, j + 1, s3, t + 1, 1, pick == 1 ? diff : diff - 1,memo);
//        }
//        memo[i][j] = ans ? 1 : 0;
//        return ans;
//    }
   public boolean isInterleave(String s1, String s2, String s3) {
       if (s1.length() + s2.length() != s3.length()) return false;
       int[][] memo=new int[s1.length()+1][s2.length()+1];
       for (int[] arr : memo) {
           Arrays.fill(arr, -1);
       }
       return isInterleave(s1, 0, s2, 0, s3,memo);
   }

    private boolean isInterleave(String s1, int i, String s2, int j, String s3,int[][] memo) {
        int t=i+j;
        if (t == s3.length()) return true;
        if(memo[i][j]!=-1) return memo[i][j] == 1;
        boolean ans = false;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(t)) {
            ans = isInterleave(s1, i + 1, s2, j, s3,memo);
        }
        if (j < s2.length() && s2.charAt(j) == s3.charAt(t)) {
            ans = ans || isInterleave(s1, i, s2, j + 1, s3,memo);
        }
        memo[i][j] = ans ? 1 : 0;
        return ans;
    }
    //https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //直接超时
//        List<LinkedList<List<Integer>>> res = new ArrayList<>();
//        for (Integer num1 : nums1) {
//            LinkedList<List<Integer>> list = new LinkedList<>();
//            for (Integer num2 : nums2) {
//              list.addLast(Arrays.asList(num1,num2));
//            }
//            res.add(list);
//        }
//        PriorityQueue<LinkedList<List<Integer>>> pq=new PriorityQueue<>(Comparator.comparingInt(a -> (a.peekFirst().get(0) + a.peekFirst().get(1))));
//        for (LinkedList<List<Integer>> linkedList : res) {
//            if(linkedList.isEmpty()) continue;
//            pq.offer(linkedList);
//        }
//        List<List<Integer>> ans=new ArrayList<>();
//        while (!pq.isEmpty()&&k-->0) {
//            LinkedList<List<Integer>> poll = pq.poll();
//            ans.add(poll.pollFirst());
//            if(!poll.isEmpty()) pq.offer(poll);
//        }
//        return ans;
      //定义一个元组出来，为什么要定义一个元组，就是要知道下一个元组，就像链表一样
        //  0,1 represents result,  2-> next num2 val
        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]+a[1]-b[0]- b[1]);
        List<List<Integer>> res = new ArrayList<>();
        int start_num2=nums2[0];
        for (int num : nums1) {
            pq.offer(new int[]{num,start_num2,0});
        }
        int cnt=0;
        while (!pq.isEmpty()&&cnt<k) {
            int[] poll = pq.poll();
            List<Integer> kvp= Arrays.asList(poll[0],poll[1]);
            int i = poll[2];
            res.add(kvp);
            cnt++;
            if(i<nums2.length-1){
                pq.offer(new int[]{poll[0],nums2[i+1],i+1});
            }
        }
        return res;
  }
  //https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/
    public int kthSmallest(int[][] matrix, int k) {
      PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            pq.offer(new int[]{row[0], i,0});
        }
        int ans=-1;
        while (!pq.isEmpty()&&k>0) {
            int[] poll = pq.poll();
            int num = poll[0];
            int row = poll[1];
            int col = poll[2];
            ans=num;
            k--;
            if(col<matrix[0].length-1){
                pq.offer(new int[]{matrix[row][col+1],row, col+1});
            }
        }
        return ans;
    }
}
